package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2020/11/27
 * @description: 二叉树后序遍历 https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
 */
public class B_145_二叉树的后序遍历 {

	/**
	 * 递归的后序遍历
	 *
	 * @param root
	 * @return
	 */
	public List<Integer> postorderTraversalByRecursive(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		postorder(root, res);
		return res;
	}

	/**
	 * 左 - 右 - 根
	 *
	 * @param node
	 * @param list
	 */
	private void postorder(TreeNode node, List<Integer> list) {
		if (node.left != null) {
			postorder(node.left, list);
		}
		if (node.right != null) {
			postorder(node.right, list);
		}
		list.add(node.val);
	}


	/**
	 * 后序遍历的迭代方式（通过草稿流程画了一遍）
	 * 但是还是标记位的问题，不能将标记位绑定在元素上面，那么我的思路就是有问题的！
	 * 还是研究一下别人的解法吧！
	 * FAIL!!!
	 *
	 * @param root
	 * @return
	 */
	public static List<Integer> postorderByIterator(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		//因为存在左节点而入栈
		Stack<TreeNode> leftStack = new Stack<>();
		//因为存在右节点而入栈
		Stack<TreeNode> rightStack = new Stack<>();
		TreeNode cur = root;
		// 是否从刚 leftStack 出来的
		boolean isVisitedLeft = false;
		// 是否从刚 rightStack 出来的
		boolean isVisitedRight = false;
		while (cur.left != null || cur.right != null || !leftStack.isEmpty() || !rightStack.isEmpty()) {

			if (cur.left != null && !isVisitedLeft) {
				leftStack.push(cur);
				cur = cur.left;
				isVisitedLeft = false;
				isVisitedRight = false;
			} else if (cur.left != null && isVisitedLeft) {
				if (cur.right != null) {
					rightStack.push(cur.right);
					cur = cur.right;
					isVisitedRight = false;
				} else {
					res.add(cur.val);
					if (!rightStack.isEmpty()) {
						cur = rightStack.pop();
						isVisitedRight = true;
					} else {
						cur = leftStack.pop();
						isVisitedLeft = true;
					}
				}
			} else if (cur.right != null && !isVisitedRight) {
				rightStack.push(cur.right);
				cur = cur.right;
				isVisitedRight = false;
			} else {
				res.add(cur.val);
				if (!rightStack.isEmpty()) {
					cur = rightStack.pop();
					isVisitedRight = true;
				} else {
					cur = leftStack.pop();
					isVisitedLeft = true;
				}
			}

		}
		return res;
	}


	/**
	 * 迭代的方法实现后序遍历
	 *
	 * @param root
	 * @return
	 */
	public static List<Integer> postorderByIteratorOffice(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		if (root == null) {
			return result;
		}
		TreeNode cur = root;
		TreeNode prev = null;
		Stack<TreeNode> stack = new Stack<>();
		while (cur != null || !stack.isEmpty()) {
			//这样找到了最左的元素
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			//此时已经是最左的元素 -> left == null
			cur = stack.pop();
			if (cur.right == null) {
				result.add(cur.val);
				prev = cur;
				cur = null;
			} else {
				//right != null
				//此时需要判断一下是否已经处理过右节点了，由于 右节点之后马上就是根节点了！
				if (cur.right == prev) {
					//此时可以处理根节点
					result.add(cur.val);
					prev = cur;
					cur = null;
				} else {
					stack.push(cur);
					cur = cur.right;
				}
			}
		}
		return result;
	}


	/**
	 * 通过迭代进行后序遍历
	 * 借助了 两个变量 readLeft + prevNode 分别判断父节点 是否已经遍历过 左子节点 和 右子节点
	 * @param root
	 * @return
	 */
	public static List<Integer> postorderByIterator2(TreeNode root) {
		List<Integer> res = new ArrayList<>();
		if (root == null) {
			return res;
		}
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		TreeNode cur = root;
		boolean readLeft = false;
		TreeNode prev = null;
		while (!stack.isEmpty()) {
			cur = stack.pop();
			while (cur.left != null && !readLeft) {
				stack.push(cur);
				cur = cur.left;
			}

			if (cur.right != null && cur.right != prev) {
				stack.push(cur);
				stack.push(cur.right);
				readLeft = false;
			} else {
				res.add(cur.val);
				prev = cur;
				readLeft = true;
			}
		}
		return res;
	}


	public static void main(String[] args) {
		TreeNode root = new TreeNode(25);
		root.left = new TreeNode(12);
		root.right = new TreeNode(35);
		root.left.left = new TreeNode(8);
		root.left.left.left = new TreeNode(5);
		root.left.left.left.left = new TreeNode(3);
		root.left.left.left.left.right = new TreeNode(4);
		root.left.left.left.right = new TreeNode(6);
		root.left.left.right = new TreeNode(9);
		root.left.left.right.right = new TreeNode(10);
		root.left.left.left.right.right = new TreeNode(11);

		root.right.left = new TreeNode(30);
		root.right.right = new TreeNode(40);

		List<Integer> list = postorderByIterator(root);
		System.out.println("list = " + list);
	}


}
